﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct ListNode {
 	int val;
 	struct ListNode *next;
 	ListNode(int x) : val(x), next(nullptr) {}
};
struct Compare {
    bool operator()(ListNode*& a, ListNode*& b) {
        return a->val > b->val; // 这里改变比较方式，反转为升序
    }
};
class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        // write code here
        priority_queue<ListNode*, std::vector<ListNode*>, Compare> qt;
        while (head)
        {
            qt.push(head);
            head = head->next;
        }
        ListNode* phead = new ListNode(0);
        ListNode* tmp = phead;
        while (qt.size())
        {
            tmp->next = qt.top();
            qt.pop();
            tmp = tmp->next;
            tmp->next = nullptr;
        }
        tmp = phead->next;
        delete phead;
        return tmp;
    }
};